package com.ronz.huffman;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;

/**
 * @Description 赫夫曼树
 * @Author Ronz
 * @Date 2021/1/20 10:32
 * @Version 1.0
 */
public class No1_HuffManTree {

    public static void main(String[] args) {
        int[] arr = {13, 7, 8, 3, 29, 6, 1};
        HuffNode root = buildHuffManTree(arr);
        root.preOrder();
    }


    public static HuffNode buildHuffManTree(int[] arr){
        // 把每个数全部转换成节点存放到 List 集合中
        ArrayList<HuffNode> nodes = new ArrayList<>();
        for (int weight : arr){
            nodes.add(new HuffNode(weight));
        }
        while (nodes.size() > 1) {
            // 将集合中节点按照权值升序排序
            Collections.sort(nodes);
            // 取出权值最小的两个节点组合成一个树
            HuffNode leftNodes = nodes.get(0);
            HuffNode rightNodes = nodes.get(1);
            HuffNode root = new HuffNode(leftNodes.weight + rightNodes.weight);
            // 建立树
            root.left = leftNodes;
            root.right = rightNodes;
            // 集合中去掉两个子节点
            nodes.remove(leftNodes);
            nodes.remove(rightNodes);

            // 把新的树添加到集合中
            nodes.add(root);
        }
        return nodes.get(0);    // 最后集合中只有一个根节点
    }

}

/**
 * 节点，实现 Comparable 接口，为了可以使用工具类进行排序
 */
class HuffNode implements Comparable<HuffNode> {
    int weight; // 权值
    HuffNode left;  // 左子节点指针
    HuffNode right; // 右子节点指针

    public HuffNode(int weight){
        this.weight = weight;
    }

    // 前序遍历：根左右
    public void preOrder(){
        System.out.println(this);
        if (this.left != null){
            this.left.preOrder();
        }
        if (this.right != null){
            this.right.preOrder();
        }
    }

    @Override
    public int compareTo(HuffNode o) {
        return this.weight - o.weight;  // 使用 权值 来排序
    }

    @Override
    public String toString() {
        return "HuffNode{" +
                "weight=" + weight +
                '}';
    }
}
